﻿//////////////////////////////////////////////////////
// 程序名称：一笔绘制金刚石图案
// 功 能：笔绘制金刚石图案，鼠标滚轮改变边数，左击开始画图，右击（在非画图状态）关闭绘图窗口
// 编译环境：Visual Studio 2017，EasyX_20190219(beta)
// 作 者：xyqlx<mxxyqlx@qq.com>
// 最后修改：2019-2-28

#include <conio.h>
#include <graphics.h>
#include <cmath>
#include <cstring>

const int N = 100;
int n = 13, top, du[N], ans[505];
bool map[N][N];
int px[N], py[N];

void Lineto(int x, int y);
void draw();

int main()
{
	// 创建绘图窗口，大小为 640x480 像素
	initgraph(640, 480);
	//填充背景为白色
	setbkcolor(WHITE);
	cleardevice();
	//设置文字颜色
	settextcolor(BLACK);
	outtextxy(200, 70, TEXT("left click:start  right click:exit  scroll:change 'n'"));
	while (true)
	{
		outtextxy(300, 100, char(48 + n / 10));
		outtextxy(308, 100, char(48 + n % 10));
		// 获取一条鼠标消息
		MOUSEMSG m = GetMouseMsg();

		switch (m.uMsg)
		{
		case WM_MOUSEWHEEL:
			if (m.wheel <= -120 && n < 99)
				n += 2;
			else if(m.wheel >= 120 && n > 5)
				n -= 2;
			break;
		case WM_LBUTTONDOWN:
			draw();
			break;

		case WM_RBUTTONUP:
			return 0;	// 按鼠标右键退出程序
		}
	}

	draw();

	_getch();              // 按任意键继续
	closegraph();          // 关闭绘图窗口
}

void dfs(int x)
{
	ans[++top] = x;
	for (int i = 0; i < n; i++)
	{
		if (map[x][i])
		{
			map[x][i] = map[i][x] = 0;
			dfs(i);
			break;
		}
	}
}

void fleury(int x)
{
	top = 1;
	ans[top] = x;
	while (top > 0)
	{
		int k = 0;
		for (int i = 0; i < n; i++)
		{
			if (map[ans[top]][i])
			{
				k = 1;
				break;
			}
		}
		if (k == 0)
		{
			Lineto(px[ans[top]],py[ans[top]]);
			top--;
		}
		else if (k == 1)
		{
			top--;
			dfs(ans[top + 1]);
		}
	}
}

void draw() {
	//证明：将要绘制的轨迹视为图，一笔画即寻找欧拉回路，由多边形（n>3）对称性可得
	//当顶点数为奇数无奇度顶点，否则有大于2个奇度顶点
	//由图论知识得当顶点数为奇数时一定有解，当顶点数为偶数时一定无解
	//构建欧拉回路的算法有Fleury算法，逐步插入回路算法等
	setfillcolor(WHITE);
	setlinecolor(WHITE);
	fillcircle(320, 240, 100);
	setlinecolor(RED);
	//PI
	float PI = float(acos(0) * 2);
	//计算
	for (int i = 0; i < n; i++) {
		px[i] = 320 + int(100 * cos(i * 2 * PI / n));
		py[i] = 240 + int(100 * sin(i * 2 * PI / n));
	}
	//fleury
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			map[i][j] = 1;
		}
		du[i] = n + 1;
		map[i][i] = 0;
	}
	moveto(px[0], py[0]);
	fleury(0);
}

void Lineto(int x, int y) {
	Sleep(200);
	static int cnt = 0;
	++cnt;
	if (cnt % 2)setlinecolor(RED);
	else setlinecolor(BLUE);
	lineto(x, y);
}